13. Text: SVD Closed Form Solution
SVD Closed Form Solution
What Is A Closed Form Solution?
A closed form solution is one where you can directly find the solution values (unlike iterative solutions, which are commonly used in practice). There isn't an iterative approach to solving a particular equation. One of the most popular examples of a closed form solution is the solution for multiple linear regression. That is if we want to find an estimate for \beta in the following situation:
y = X\beta
We can find it by computing the Best Linear Unbiased Estimate (BLUE). It can be found in closed form using the equation:
\hat{\beta} = (X'X)^-X'y
where X is a matrix of explanatory inputs and y is a response vector.
Another common example of a closed form solution is the quadratic equation. If we want to find x that solves:
ax^2 + bx + c = 0
We can find these values using the quadratic formula:
x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}
Each of these is an example of a closed form solution, because in each case we have an equation that allows us to solve directly for our values of interest.
Closed Form Solutions for SVD
It turns out there is a closed form solution for Singular Value Decomposition that can be used to identify each of the matrices of interest (U, \Sigma, V). The most straightforward explanation of this closed form solution can be found at this MIT link.
As put in the paper -
"Calculating the SVD consists of finding the eigenvalues and eigenvectors of AA' and A'A. The eigenvectors of A'A make up the columns of V , the eigenvectors of AA' make up the columns of U. Also, the singular values in \Sigma are square roots of eigenvalues from AA' or A'A. The singular values are the diagonal entries of the \sigma matrix and are arranged in descending order. The singular values are always real numbers. If the matrix A is a real matrix, then U and V are also real."
Again, you can see a fully worked example of the closed form solution at the MIT Link here.
A More Common Approach
The main issue with the closed form solution (especially for us) is that it doesn't actually work when we have missing data. Instead, Simon Funk (and then many followers) came up with other solutions for finding our matrices of interest in these cases using gradient descent.
So all of this is to say, people don't really use the closed form solution for SVD, and therefore, we aren't going to spend a lot of time on it either. The link above is all you need to know. Now, we are going to look at the main way that the matrices in SVD are estimated, as this is what is used for estimating values in FunkSVD.
Additional Resources
Below are some additional resources in case you are looking for others that go beyond what was shown in the simplified MIT paper.